package com.gitee.feizns.explore.data_structure.tree.bs.easy;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 637. 二叉树的层平均值
 * @author feizns
 * @since 2020/1/4
 */
public class AverageOfLevels {

    public static void main(String[] args) {
        List<Double> doubles = averageOfLevels(create());
        System.out.println(doubles);
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(3);
        ret.left = new TreeNode(9);
        ret.right = new TreeNode(20);
        ret.left.left = new TreeNode(15);
        ret.left.right = new TreeNode(7);
        return ret;
    }

    public static List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        return averageOfLevels(new LinkedList<>(), queue);
    }

    private static List<Double> averageOfLevels(List<Double> list, Queue<TreeNode> queue) {
        Queue<TreeNode> newQueue = new LinkedList();
        double sum = 0;
        int size = queue.size();
        while ( !queue.isEmpty() ) {
            TreeNode node = queue.remove();
            sum += node.val;
            if ( node.left != null )
                newQueue.add(node.left);
            if ( node.right != null )
                newQueue.add(node.right);
        }
        list.add(sum / size);
        if ( !newQueue.isEmpty() )
            averageOfLevels(list, newQueue);
        return list;
    }

}
